#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

class LRUCache {
private:
    struct LinkedList {

        int key[200010];
        int value[200010];
        int left[200010];
        int right[200010];

        int idx;
        int head, tail;

        LinkedList() {
            idx = 2;
            head = -1;
            tail = -1;
//        memset(node.va, -1, 200000);
        }

        void link(int x, int y) {
            right[x] = y;
            left[y] = x;
        }


        void add_behind_tail(int k, int v) {
            key[idx] = k;
            value[idx] = v;

            left[idx] = -1;
            right[idx] = -1;

            if (head == -1) {
                head = tail = idx;
            } else {
                link(tail, idx);
                tail = idx;
            }
            idx++;

        }


        void remove_node_by_address(int node) {
            if(node == head){
                remove_head();
            }else if (node == tail){
                remove_tail();
            }else {
                link(left[node], right[node]);
            }
        }

        void remove_head() {
            if(head == tail){
                head = tail = -1;
            } else {
                key[head] = -1;
                value[head] = -1;
                head = right[head];
                left[head] = -1;
            }
        }

        void remove_tail(){
            if(head == tail){
                head = tail = -1;
            }else{
                tail = left[tail];
                right[tail] = -1;
            }
        }
    };

    int hashTable[11000];
    int size;
    int capacity;
    LinkedList linkedList;



public:
    LRUCache(int capacity) : size(0), capacity(capacity) {
        memset(hashTable, -1, sizeof(hashTable));
    }

    int get(int key) {
        int address = hashTable[key];

        if(address != -1){
            int k = linkedList.key[hashTable[key]];
            int v = linkedList.value[hashTable[key]];

            /* move to end */
            linkedList.remove_node_by_address(hashTable[key]);
            linkedList.add_behind_tail(k, v);
            hashTable[key] = linkedList.tail;

            return v;
        }

        return -1;
    }

    void put(int key, int value) {
        linkedList.add_behind_tail(key, value);

        if (hashTable[key] != -1) {
            /* 覆盖 */
            linkedList.remove_node_by_address(hashTable[key]);
            hashTable[key] = linkedList.tail;
            return;
        }

        hashTable[key] = linkedList.tail;
        size++;

        if (size > capacity) {
            /* 头删 */
            int k = linkedList.key[linkedList.head];
            linkedList.remove_head();
            hashTable[k] = -1;
            size--;
        }
    }

};





using namespace std;
int main() {

    LRUCache lRUCache(10000);
    lRUCache.put(1, 1);
    lRUCache.put(2, 2);
    cout << lRUCache.get(1) << endl;
    cout << lRUCache.get(3) << endl;
    cout << lRUCache.get(4) << endl;
    lRUCache.put(3, 3);
    lRUCache.put(4, 4);
    lRUCache.put(3, 4);
    lRUCache.put(12, 4);
    lRUCache.put(1214, 7);
    lRUCache.put(4325, 7);
    lRUCache.put(6454, 7);
    lRUCache.put(3454, 7);
    lRUCache.put(4624, 7);
    lRUCache.put(9544, 7);
    lRUCache.put(1634, 7);
    lRUCache.put(6274, 7);
    lRUCache.put(9024, 7);
    lRUCache.put(8152, 7);
    lRUCache.put(7824, 7);
    lRUCache.put(8244, 4);
    lRUCache.put(2114, 4);
    lRUCache.put(3144, 4);
    lRUCache.put(8924, 4);
    lRUCache.put(9024, 4);

    cout << lRUCache.get(9024) << endl;

    return 0;
}
